/************************************************************
 * Project Name         [Thinking_In_Java]
 * File Name            [Primes2.java]
 * Creation Date        [02-Jul-2014]
 * 
 * Copyright© ge.y.yang@gmail.com All Rights Reserved
 * 
 * Work hard, play harder, think big and keep fit
 ************************************************************/
package pkg_algorithm;

import java.util.Arrays;

/**
 * 求指定范围内的质数
 * 
 * @author 不落的太阳(Sean Yang)
 * @version 1.0
 * @since JDK 6
 * 
 */
public class Primes2 {

	/**
	 * 显示range范围内的质数
	 * 
	 * @param range
	 */
	public void showPrimeNumber(int range) {
		boolean[] primes = sieve(range);
		int number = 0;
		if (primes != null) {
			System.out.println("范围在" + range + "内的质数个数有: ");
			for (int i = 1; i < primes.length; i++) {
				if (primes[i]) {
					System.out.print(i + "  ");
					// 每输出10个质数换行
					if (++number % 10 == 0) {
						System.out.println();
					}
				}
			}
			System.out.println();
		}
		System.out.println("一共有" + number + "个");
	}

	/**
	 * 筛选法求质数
	 * 
	 * @param range
	 * @return 所在范围内质数的数组
	 */
	private boolean[] sieve(int range) {
		if (range <= 0) {
			System.out.println("求质数的范围range必须大于0!");
			return null;
		}
		// 用一个布尔数组标示是否为质数, 如果下标值为质数, 那么该下标值对应的数组元素的值为true
		// 如2是质数, isPrime[2] = true, 因为数组是下标是从0开始的, 所以这里新建的数组大小为range+1
		boolean[] isPrime = new boolean[range + 1];
		// 1不是质数
		isPrime[1] = false;
		// 用Arrays的fill方法将数组下标从2到range+1之间的元素的值都赋为true
		Arrays.fill(isPrime, 2, range + 1, true);
		// Math的sqrt方法用于求开方
		int n = (int) Math.sqrt(range);
		for (int i = 1; i <= n; i++) {
			if (isPrime[i]) {
				// 如果i是质数, 那么i的倍数不是质数
				for (int j = 2 * i; j <= range; j += i) {
					isPrime[j] = false;
				}
			}
		}
		return isPrime;
	}

	/**
	 * 测试方法
	 * 
	 * @param args
	 *            命令行参数
	 */
	public static void main(String[] args) {
		int range = 200;
		new Primes2().showPrimeNumber(range);
	}
}
